package LeetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LC_451_SortCharactersByFrequency {

    public static void main(String[] args) {

    }


    public class Solution {

        @SuppressWarnings("unchecked")
        public String frequencySort(String s) {
            if (s == null) return null;
            Map<Character, Integer> map = new HashMap();
            char[] charArray = s.toCharArray();
            int max = 0;
            for (Character c : charArray) {
                if (!map.containsKey(c)) map.put(c, 0);
                map.put(c, map.get(c) + 1);
                max = Math.max(max, map.get(c));
            }
            List<Character>[] array = buildArray(map, max);

            return buildString(array);
        }

        @SuppressWarnings("unchecked")
        private List<Character>[] buildArray(Map<Character, Integer> map, int maxCount) {
            List<Character>[] array = new List[maxCount + 1];
            for (Character c : map.keySet()) {
                int count = map.get(c);
                if (array[count] == null)
                    array[count] = new ArrayList();
                array[count].add(c);
            }
            return array;
        }

        private String buildString(List<Character>[] array) {
            StringBuilder sb = new StringBuilder();
            for (int i = array.length - 1; i > 0; i--) {
                List<Character> list = array[i];
                if (list != null) {
                    for (Character c : list) {
                        for (int j = 0; j < i; j++) {
                            sb.append(c);
                        }
                    }
                }
            }
            return sb.toString();
        }

    }

    static class Solution_2 {

        public String frequencySort(String s) {
            char[] arr = s.toCharArray();
            String[][] record = new String[arr.length][2];
            int num = 0;
            for (char anArr : arr) {
                int j = 0;
                boolean hasFind = false;
                for (; j < num; j++) {
                    if (anArr - record[j][0].charAt(0) == 0) {
                        hasFind = true;
                        int temp = Integer.parseInt(record[j][1]) + 1;
                        record[j][1] = Integer.toString(temp);
                        break;
                    }
                }
                if (!hasFind) {
                    record[j][0] = String.valueOf(anArr);
                    record[j][1] = "1";
                    num++;
                }
            }
            for (int i = 0; i < num; i++) {
                for (int j = 0; j < num - 1; j++) {
                    String[] temp;
                    if (Integer.parseInt(record[j][1]) - Integer.parseInt(record[j + 1][1]) > 0) {
                        temp = record[j];
                        record[j] = record[j + 1];
                        record[j + 1] = temp;
                    }
                }
            }
            StringBuilder result = new StringBuilder();
            for (int i = num - 1; i >= 0; i--) {
                System.out.println(record[i][1]);
                System.out.println(record[i][0]);
                for (int j = 0; j < Integer.parseInt(record[i][1]); j++) {
                    result.append(record[i][0]);
                }
            }
            return result.toString();
        }

    }
}